package com.atguigui.leetcode;

/**
 * 1175.质数排列
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/30 8:39
 */
public class P1175PrimeArrangements {
    public static void main(String[] args) {
        Solution solution = new P1175PrimeArrangements().new Solution();
        // TO TEST
    }

    class Solution {
        static final int MOD = 1000000007;

        /**
         * 阶乘、质数
         * 试除法
         *
         * @param n
         * @return
         */
        public int numPrimeArrangements(int n) {
            int numPrimes = 0;
            for (int i = 1; i <= n; i++) {
                if (isPrime(i)) {
                    numPrimes++;
                }
            }
            // factorial(numPrimes):所有质数的阶乘
            // factorial(n - numPrimes):所有合数的阶乘
            return (int) (factorial(numPrimes) * factorial(n - numPrimes) % MOD);

        }

        /**
         * 阶乘
         *
         * @param n
         * @return
         */
        private long factorial(int n) {
            long res = 1;
            for (int i = 1; i <= n; i++) {
                res *= i;
                res %= MOD;
            }
            return res;
        }

        /**
         * 判断是否是质数
         *
         * @param n
         * @return
         */
        private boolean isPrime(int n) {
            // 1不是质数
            if (n == 1) {
                return false;
            }
            // 除了1和它本身，都不能被其他数整除的数为质数
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }
}
